package com.zdp.leetcodeMiddle;


import com.zdp.util.ListNode;

/*
* 题目描述：
* 对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insertion-sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 对链表进行插入排序_147 {
    public static void main(String[] args) {
        对链表进行插入排序_147 demo = new 对链表进行插入排序_147();
        ListNode head = ListNode.createListNode(4,2,1,3);
        ListNode listNode = demo.insertionSortList(head);
        ListNode.staticSoutList(listNode);
    }

    /*
    * 解题思路： 关于插入排序： 就是将数组分为两部分 ，一部分为已排序
    * 一部分为 未排序， 将未排序的元素插入到已排序的元素中
    *  只要从尾部开始比较即可 （因为 要插入的数组是以排序的）
    * 难点： 链表是单向的 怎么找到前面的呢
    * */
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = head.next;
        ListNode Ppre = head;
        ListNode root = new ListNode();
        ListNode pre = root;
        root.next = head;
        ListNode next = head;
        while(p != null){
            // 开始进行插入
            // 找到要插入的位置
            while(next.val <= p.val && next != p){
                pre = next;
                next = next.next;
            }
            // 进行插入
            // 先删除  再插入
            // Ppre 表示的 是 已排序链表部分的尾部
            Ppre.next = p.next;
            p.next = pre.next;
            pre.next = p;
            if(next == p){
                Ppre = Ppre.next;
                p = Ppre.next;
            }else{
                p = Ppre.next;
            }
            pre = root;
            next = root.next;
        }
        return root.next;
    }
}
